﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace 九连环
{
    class Program
    {
        static void Main(string[] args)
        {
            DateTime start = DateTime.Now;
            Console.WriteLine("求解开始");
            Console.WriteLine();

            Solution solution = new(9);
            bool over = false;

            Queue<Solution> queue = new();
            queue.Enqueue(solution);

            HashSet<int> set = new();
            set.Add(solution.Key());

            while (queue.Any())
            {
                Solution now = queue.Dequeue();

                var steps = now.Steps();
                foreach(var step in steps)
                {
                    Solution next = new(now, step);
                    if (next.Succes())
                    {
                        over = true;
                        Print(next);
                        break;
                    }

                    int key = next.Key();
                    if (set.Add(key))
                    {
                        queue.Enqueue(next);
                    }
                }

                if (over)
                {
                    break;
                }
            }


            DateTime end = DateTime.Now;
            Console.WriteLine();
            Console.WriteLine("求解结束");

            Console.WriteLine($"耗时:{(end - start).TotalMilliseconds}毫秒");
        }

        static void Print(Solution solution)
        {
            if (solution.parent != null)
            {
                Print(solution.parent);
            }

            if (solution.th > 0)
            {
                Console.WriteLine($"第{solution.th}步: 动第【 {solution.step + 1} 】个环");
            }
        }
    }
}
